Ferrous ion and 2-oxoglutarate (2OG) oxygenases catalyze the demethylation of N(epsilon)-methylated lysine residues in histones. Here we report studies on the inhibition of the JMJD2 subfamily of histone demethylases, employing binding analyses by nondenaturing mass spectrometry (MS), dynamic combinatorial chemistry coupled to MS, turnover assays, and crystallography. The results of initial binding and inhibition assays directed the production and analysis of a set of N-oxalyl-d-tyrosine derivatives to explore the extent of a subpocket at the JMJD2 active site. Some of the inhibitors were shown to be selective for JMJD2 over the hypoxia-inducible factor prolyl hydroxylase PHD2. A crystal structure of JMJD2A in complex with one of the potent inhibitors was obtained; modeling other inhibitors based on this structure predicts interactions that enable improved inhibition for some compounds.